package com.leetcode.LC_MED;

import java.util.ArrayList;

public class LC234 {
    public boolean isPalindrome(ListNode head) {

        ArrayList<Integer> list = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            list.add(tmp.val);
            tmp = tmp.next;
        }
        for (Integer integer : list) {
            System.out.print(integer);
        }
        int a = 0, b = list.size() - 1;
        while (a < b) {
            if (!list.get(a).equals(list.get(b))) {
                return false;
            }
            a++;
            b--;
        }
        return true;
    }

    //其一，find mid node 使用快慢指针找到链表中点。 其二，reverse 逆序后半部分。 其三，check 从头、中点，开始比较是否相同。
    public boolean isPalindrome2(ListNode head) {

        if (head == null || head.next == null) {
            return true;
        }

        ListNode fast = head;
        ListNode slow = head;

        // 根据快慢指针，找到链表的中点
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        slow = reverse(slow.next);
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }

    private ListNode reverse(ListNode head) {
        //递归到最后一个节点，返回新的的头节点
        if (head.next == null) {
            return head;
        }
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
